package com.zlsy.learning.leetcode.linkedlist.l234;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhouliang
 * @date 2020/8/3 13:59
 */
public class IsPalindrome {
  public static void main(String[] args) {
    ListNode listNode = new ListNode(1);
    listNode.add(2);
    listNode.add(3);
    listNode.add(2);
    listNode.add(1);
    listNode.print();

    boolean palindrome = isPalindromeBySpeedPointer(listNode);
    System.out.println(palindrome);
  }

  /**
   * 数据复制
   *
   * @param head
   * @return
   */
  public static boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    ListNode currentNode = head;

    // N个数据规模执行N次，时间复杂度O（n）
    while (currentNode != null) {
      // 空间复杂O（n）
      vals.add(currentNode.val);
      currentNode = currentNode.next;
    }

    int front = 0;
    int back = vals.size() - 1;
    // 从链表的头和屁股开始向中间找
    while (front < back) {
      // 如果头尾每两个都是相等的数，就是回文数
      if (!vals.get(front).equals(vals.get(back))) {
        return false;
      }
      front++;
      back--;
    }

    return true;
  }

  /**
   * 回文链表-快慢指针
   *
   * @param head
   * @return
   */
  public static boolean isPalindromeBySpeedPointer(ListNode head) {
    if (head == null) {
      return true;
    }
    // 中心位置
    ListNode firstHalfEnd = endOfFirstHalf(head);
    ListNode secondHalfStart = reverseList1(firstHalfEnd.next);

    ListNode p1 = head;
    ListNode p2 = secondHalfStart;

    boolean result = true;
    while (result && p2 != null) {
      if (p1.val != p2.val) {
        result = false;
      }
      p1 = p1.next;
      p2 = p2.next;
    }

    // 再次反转链表
    firstHalfEnd.next = reverseList(secondHalfStart);

    return result;
  }

  /**
   * 取中心点（这里取的是上中位，就是如果是奇数那么中心很好找，如果是偶数，比如1、2、2、1，取得是第二位的2，因为是用fast来判断的。）
   *
   * @param head
   * @return
   */
  private static ListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    // 如果快指针走两步不能为空，（需判断第一步是否为空）。
    while (fast.next != null && fast.next.next != null) {
      // 定义快指针= next.next（走两步）
      fast = fast.next.next;
      // 定义man指针= next（走一步）
      slow = slow.next;
    }
    return slow;
  }

  /** 单链表反转 - 头插入法 */
  private static ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
      ListNode nextTemp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = nextTemp;
    }
    return prev;
  }

  /** 单链表反转 - 就地反转 */
  private static ListNode reverseList1(ListNode head) {
    if (head == null) {
      return head;
    }
    ListNode prev = head;
    ListNode pCur = head.next;

    while (pCur != null) {
      // 摘除 234null 34null = 134null;pCur=234null
      prev.next = pCur.next;
      // 放入头节点
      pCur.next = head;
      // 更新链表
      head = pCur;
      // 设置下次要变化的值
      pCur = prev.next;
    }

    return head;
  }
}
